package org.example.ch04;

import org.example.ch04.tree.ConstructTree;
import org.example.ch04.tree.TreeNode;
import sun.reflect.generics.tree.Tree;

public class lowestCommonAncestor {

    public static void main(String[] args) {
        TreeNode root = ConstructTree.constructTree(new Integer[]{3,5,1,6,2,0,8,null,null,7,4});
        TreeNode p = new TreeNode(17);
        TreeNode q = new TreeNode(52);
        TreeNode result= solution(root,p,q);
        System.out.println(result==null?"":result.val);

    }

    public static TreeNode solution(TreeNode root,TreeNode p,TreeNode q) {
       //递归的终结条件
        if(root==null){
            return null;
        }
        //执行本层逻辑
        if(root.val == p.val||root.val==q.val){
            return root;
        }
        //下探到下一层递归
        TreeNode left = solution(root.left,p,q);
        TreeNode right = solution(root.right,p,q);
        if(left!=null && right!=null){
            return root;
        }
        if(left==null){
            return right;
        }
        if(right==null){
            return left;
        }
        //清理本层
        return null;
    }
}
